package arithmetic.demo14;


import  java.util.*;

/**
 * 题目： floodfill算法_图像渲染
 */
class Solution {
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    boolean[][] path ;
    int  row ;
    int  col ;
    int tmp;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 初始化
        row = image.length;
        col= image[0].length;
        path = new boolean[row][col];
        int[][] ret = new int[row][col];
        

        // 自身修改
        tmp = image[sr][sc];
        path[sr][sc] = true;

        // 递归
        dfs(image, sr, sc);

        // 开始修改
        for(int i = 0; i< row; i++) {
            for(int j = 0; j < col ; j++) {
                // 遇到的就修好为 color
                if(path[i][j]) {
                    ret[i][j]= color;
                } else {
                    // 没遇到就赋值原数
                    ret[i][j] = image[i][j];
                }
            }
        }

        return ret;
    }

    public void dfs(int[][] image , int i, int j ) {
            
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];

                // 开始深搜
                if(x >= 0 && x < row && y >= 0 && y < col 
                && tmp == image[x][y] && !path[x][y]) {
                    path[x][y] =  true;
                    dfs(image, x , y);            
                }

                // 这里不需要剪枝
            }
    }
   
}


/**
 * 题目: floodfill_岛屿数量
 */

class Solution1{
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    boolean[][] path;
    int row, col;
    public int numIslands(char[][] grid) {
        // 初始化
        row = grid.length;
        col = grid[0].length;
        path = new  boolean[row][col];

        // 用于记录结果
        int ret = 0;

        // 遍历没有走过的岛屿
        for(int i =0; i<row; i++) {
            for(int j =0; j<col; j++) {
                // 只要没走过，就进行深搜
                if(grid[i][j] == '1' && !path[i][j]) {
                    ret++;
                    path[i][j] = true;
                    dfs(grid, i, j);
                }
            }
        }


        return ret;

    }


    // 开始深搜
    public void dfs(char[][] grid, int i , int j ) {
        for(int  k =0; k<4; k++){
            int x = i + dx[k], y = j + dy[k];
            // 四个方位探索
            if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1' && !path[x][y]) {
                path[x][y] = true;
                dfs(grid, x, y);
            }

            // 不需要回溯
        }
    }
}

/**
 * 题目: floodfill_岛屿的最大面积
 */


class Solution2 {
    int[] dx = {0,0, -1,1};
    int[] dy = {-1,1,0,0};
    int row  , col;
    boolean[][] path;

    int count ;
    public int maxAreaOfIsland(int[][] grid) {
        // 初始化
        row = grid.length;
        col = grid[0].length;
        path = new boolean[row][col];

        int ret = 0;

        // 记录最大岛屿
        // 上下左右四个方位搜索
        for(int i =0; i<row; i++) {
            for(int j = 0; j<col ; j++) {
                // 开始递归
                if(grid[i][j] == 1 && !path[i][j]) {
                    count = 1;
                    path[i][j] = true;
                    dfs(grid, i, j);
                    ret = Math.max(ret, count);
                }
            }
        }


        return ret;
    }


    public void dfs(int[][] grid , int i, int j ) {
        for(int k = 0; k<4; k++) {
            int x = i + dx[k] , y = j + dy[k];
            // 剪枝
            if(x >= 0 && x < row && y >= 0 && y < col && !path[x][y] &&
                    grid[x][y] == 1) {
                path[x][y] = true;
                count++;
                // 深搜
                dfs(grid, x, y);
            }
        }
    }
}


/**
 *  题目： floodfill_被环绕的区域
 */

class Solution3 {
    int[] dx = {0,0,-1,1};
    int[] dy = {-1, 1, 0,0};
    int row , col ;
    public void solve(char[][] board) {
        // 初始化
        row = board.length;
        col = board[0].length;


        // 先寻找边界值

        // 左边界和右边界
        for(int i = 0 ; i < row ; i++) {
            // 左边界
            if(board[i][0] == 'O') {
                board[i][0] = '#';
                dfs(board, i , 0);
            }
            // 右边界
            if(board[i][col - 1] == 'O') {
                board[i][col - 1] = '#';
                dfs(board,  i , col -1);
            }
        }


        // 上边界和下边界
        for(int j = 0 ; j < col ; j++) {
            // 上边界
            if(board[0][j] == 'O') {
                board[0][j] = '#';
                dfs(board, 0 , j);
            }

            // 下边界
            if(board[row -1 ][j] == 'O') {
                board[row - 1 ][j] = '#';
                dfs(board, row -1 , j);
            }
        }


        // 进行修改
        for(int i =0 ; i < row ; i++) {
            for(int j =  0; j<col ; j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if( board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }



    }


    public void dfs(char[][] board, int i , int j) {
        for(int   k  =0; k < 4; k++) {
            int x = i + dx[k] , y = j + dy[k];
            // 进行剪枝
            if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'O' ) {
                board[x][y] = '#';
                dfs(board,  x, y);
            }
        }
    }


}





class Solution5 {
    int[] dx = {0,0, -1, 1};
    int[] dy = {-1,1,0,0};
    boolean[][] path ;
    int row , col;
    int  ret ;

    int beginx , beginy ;
    public int nearestExit(char[][] maze, int[] entrance) {
        // 初始化
        row = maze.length;
        col = maze[0].length;
        path= new boolean[row][col];
        ret = Integer.MAX_VALUE;
        beginx =  entrance[0]; beginy = entrance[1];

        // 开始递归
        dfs(maze,beginx, beginy, 0);

        return ret == Integer.MAX_VALUE ? -1 : ret ;
    }

    public void dfs(char[][] maze, int i , int j, int step) {
        path[i][j] = true;

        // 判断当前位置是否是边界位置
        if( !(i == beginx && j == beginy )&&  (i == 0 || i == row - 1 || j == 0 || j == col - 1)) {
            ret = Math.min(ret, step);
            return;
        }

        // 上下左右方位搜索
        for(int  k = 0 ; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            // 进行剪枝
            if(x >= 0 && x < row && y >= 0 && y < col
                    && maze[x][y] == '.' && !path[x][y]) {
                dfs(maze, x, y ,step + 1 );

                // 恢复现场
                path[x][y] = false;
            }
        }


    }


}


/**
 * 题目： BFS算法_迷宫中离入口最近的出口
 */

class Solution4 {
    int[] dx = {0,0, -1, 1};
    int[] dy = {-1,1,0,0};
    int row , col;


    public int nearestExit(char[][] maze, int[] entrance) {
        row = maze.length;
        col = maze[0].length;

        boolean[][] path = new boolean[row][col];

        int ret = Integer.MAX_VALUE;

        Queue<int[]> queue = new LinkedList<>();
        path[entrance[0]][entrance[1]] = true;

        // 初始化
        queue.add(entrance);

        int count = 1;
        while(!queue.isEmpty()) {
            int sz= queue.size();
            // 得到节点
            for(int i =0; i<sz ; i++) {
                int[] tmp = queue.poll();
                for(int k = 0; k < 4; k++) {
                    int x = tmp[0] + dx[k];
                    int y = tmp[1] + dy[k];
                    //    剪枝
                    if(x >= 0 && x < row && y >= 0 && y < col
                            && maze[x][y] == '.' && !path[x][y]) {
                        path[x][y] = true;
                        queue.add(new int[]{x,y});

                        // 判断是否是结果
                        if(x == 0 || x == row -1 ||
                                y == 0 || y == col -1 ) {
                            ret = Math.min(ret, count);
                        }
                    }


                }

            }

            count++;
        }





        return ret == Integer.MAX_VALUE  ? -1 : ret ;
    }

}


class Test {
    public static void main(String[] args) {
        Solution4 solution4  = new Solution4();
        int[] index = {1,0};
        char[][] str = {{'+','+','+'},{'.','.','.'},{'+','+','+'}};
        System.out.println(solution4.nearestExit(str, index));
    }
}

